package ac;

public class KMP {
    private final String pattern;
    private int[] nextTable;

    public KMP(final String pattern) {
        this.pattern = pattern;
        buildNextTable();
    }

    public boolean containsMatch(final String target) {
        for (int i = 0, j = 0; i < target.length(); i++) {
            if (j > 0 && target.charAt(i) != pattern.charAt(j)) {
                j = nextTable[j - 1];
            }
            if (target.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                return true;
            }
        }
        return false;
    }

    private void buildNextTable() {
        nextTable = new int[pattern.length()];
        nextTable[0] = 0;
        for (int i = 1, j = 0; i < pattern.length(); i++) {
            if (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
                j = nextTable[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            nextTable[i] = j;
        }
    }
}
